package SubjectTree.One;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import Utility.TreeNode;

public class AverageOfLevels {

/**
 * 难度：简单
 * 
 * 637. 二叉树的层平均值
 * 	给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
 * 
 * 示例 1：
 * 	输入：
 * 	    3
 * 	   / \
 * 	  9  20
 * 	    /  \
 * 	   15   7
 * 	输出：[3, 14.5, 11]
 * 	解释：
 * 	第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
 * 	
 * 提示：
 * 	节点值的范围在32位有符号整数范围内。
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		AverageOfLevels aol = new AverageOfLevels();
		TreeNode root = TreeNode.MkTree("[3,9,20,null,null,15,7]");
		System.out.println(aol.averageOfLevels(root));
	}

	public List<Double> averageOfLevels(TreeNode root) {
		List<Double> ret = new ArrayList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()) {
			int currentLevelSize = queue.size();
			double count = 0;
			for(int i=0;i<currentLevelSize;i++) {
				TreeNode node = queue.poll();
				count += node.val;
				if(node.left != null) queue.offer(node.left);
				if(node.right != null) queue.offer(node.right);
			}
			ret.add(count/currentLevelSize);
		}
		return ret;
    }
}
